package Sequence;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test0763 {
    public static void main(String[] args)
    {
        Solution0763_2 solution = new Solution0763_2();
        String s = "ababcbacadefegdehijhklij";
        System.out.println(solution.partitionLabels(s));
    }
}

class Solution0763_1 {
    public List<Integer> partitionLabels(String s) {
        int length = s.length();
        char[] chars = s.toCharArray();

        int[] records = new int[26];
        Arrays.fill(records,-1);

        ArrayList<Integer> ans = new ArrayList<>();

        for (int i = 0; i < length; i++) {
            int record = records[chars[i] - 'a'];

            if (record != -1)
                while (!ans.isEmpty()&&record<=ans.get(ans.size()-1))
                    ans.remove(ans.size()-1);
            else
                records[chars[i] - 'a'] = i;

            ans.add(i);
        }

        int size = ans.size();
        for (int i = size-1;i>0; i--) ans.set(i,ans.get(i)-ans.get(i-1));
        ans.set(0,ans.get(0)+1);

        return ans;
    }
}

class Solution0763_2 {
    public List<Integer> partitionLabels(String s) {
        int[] record = new int[26];
        Arrays.fill(record,-1);
        char[] chars = s.toCharArray();

        ArrayDeque<Integer> deque = new ArrayDeque<>();
        ArrayList<Integer> ans = new ArrayList<>();
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            int index = c - 'a';

            if (record[index] == -1){
                record[index] = i;
                deque.offer(i);
            } else {
                int last = record[index];
                while (deque.peekLast()>last){
                    deque.pollLast();
                }
            }
        }

        int limit = deque.poll();
        while (!deque.isEmpty()){
            int index = deque.poll();

            ans.add(index-limit);
            limit = index;
        }
        ans.add(chars.length-limit);
        return ans;
    }
}

class Solution0763_3 {
    public List<Integer> partitionLabels(String s) {
        int[] record = new int[26];
        char[] chars = s.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            int index = c - 'a';
            record[index] = i+1;
        }

        ArrayList<Integer> ans = new ArrayList<>();
        int start = 1,end = record[chars[0]-'a'];
        for (int i = 1; i < chars.length; i++) {
            if (i==end){
                ans.add(end-start+1);
                start = i+1;
                end = record[chars[i]-'a'];
            } else {
                end = Math.max(end,record[chars[i]-'a']);
            }
        }

        ans.add(end-start+1);
        return ans;
    }
}
